Public key cryptography is used to generate and verify the validity of digital signatures. A digital signature algorithm requires a private key, which is known only by the signer, and a public key, which can be made available to anyone that may need to verify the signature. A digital message is signed using the signer's private key, and a digital signature's validity is verified using the signer's public key. A valid digital signature authenticates the identity of the signer and the integrity of the digital message. If the digital signature fails the verification test then the digital signature is considered invalid. An invalid signature does not provide any assurance to the verifier of the identity of the signer or the integrity of the message. An invalid signature may be the result of an intentional modification or substitution of the digital message or digital signature, or may be the result of an unintentional modification, such as a transmission error.
Testing each digital signature in a large group (i.e., a batch) of digital signatures individually for validity may be too time consuming for many applications. It is often possible to test the validity of digital signatures as a batch. Batch verification can be much less time intensive than individual verification of digital signatures. If all of the digital signatures in a batch are valid, then the batch is valid and will pass the batch verification test. If at least one digital signature in the batch is invalid, then the batch is invalid and will fail the verification test. If a batch is invalid and one wants to know which digital signatures within the batch are invalid then at least some further verification testing is required. Present methods of identifying invalid digital signatures in large batches may be too time consuming for many applications. Therefore, there is a need for a time efficient method of identifying invalid digital signatures in batches. The present invention is such a method.
Three methods of verifying a batch of digital signatures is disclosed in a paper by Mihir Bellare et al, entitled “Fast Batch Verification for Modular Exponentiation and Digital Signatures,” Advances in Cryptography—Eurocrypt 98 Proceedings, LCNS, Vol. 1403, pp. 236-250, Springer-Verlag, 1998. One of these methods is known as the “small exponents test.” The first step of the method is receiving a number of digital messages, digital signatures, and signer identifiers, where the digital signatures were generated using a generator g. The second step of the method is computing first and second numeric values corresponding to the digital messages, digitals signatures, and signer identifiers. The third step of the method is selecting a number of random numbers equal to the number of digital signatures. The fourth step of the method is associating each random number with a digital signature. The fifth step of the method is multiplying each first numeric value by its corresponding random number. The sixth step of the method is summing the products of the fifth step. The seventh step of the method is raising each second numeric value to a power, where the power is the corresponding random number. The eighth step of the method is multiplying the results of the seventh step. The ninth step of the method is raising g to the result of the sixth step. The tenth step of the method is comparing the results of the eighth and ninth steps. If the results are equal then the batch is valid and all of the digital signatures therein are valid. Otherwise, the batch is invalid and at least one digital signature therein is invalid.
If a batch of digital signatures is invalid then it is often necessary to identify the invalid digital signatures that caused the batch to fail. The naïve method is to perform an individual verification test on each digital signature in the batch. This requires as many verification tests as there are digital signatures in the batch, which may be too time consuming for many applications that require large numbers of digital signatures.
Divide-and conquer approaches (also know as “cut-and-choose” approaches) that reduce the number of verifications tests required to identify invalid digital signatures in an invalid batch are disclosed in a paper by J. Pastuszak et al., entitled “Identification of Bad Signatures in Batches,” Public Key Cryptography—PKC 2000, LCNS 1751, pp. 28-45, Springer-Verlag, 2000. That is, a verification test is performed on the original batch. If the batch is valid then stop. Otherwise, divide the batch into smaller batches. Then, perform a verification test on each smaller batch, eliminating the smaller batches that are valid, and further dividing the smaller batches that were invalid. Eventually, this technique will lead to the individual digital signatures that caused the original batch to fail the verification test. If each batch to be divided is halved, the divide-and-conquer approach becomes a binary search. In most cases, divide-and-conquer methods identify invalid digital signature more quickly than the naïve method. However, in some applications, identifying invalid signatures is still too time consuming. Therefore, a faster method of identifying invalid signatures is needed. The present invention is such a method.
Some prior art digital signature methods are based on bilinear pairings, because the mathematical properties of such pairings can be used to generate digital signatures that are either shorter or facilitate the identification of the signer. Digital signatures that employ bilinear pairings are commonly referred to as pairing-based digital signatures. Digital signatures that facilitate the identification of the sender are commonly referred to as identity-based digital signatures. Identity-based digital signatures are public key digital signatures in which the verifier can compute the signer's public key directly from the signer's identifier. This eliminates the need to generate and manage digital certificates, which bind signer's identifiers to their public keys. It also eliminates the need to transmit a public key or a digital certificate. However, verification of identity-based digital signatures often involves bilinear-pairing operations, which are more computationally intensive than other operations. Verifying a large batch of identity-based digital signatures is often prohibitive using prior art methods, including divide-and-conquer methods. Therefore, there is a need for a batch verification method for identity-based digital signatures that requires fewer computations. The present invention is such a method.
In an article entitled “An Identity-Based Signature from Gap Diffie-Hellman Groups,” by J. Cha and J. Cheon, Public Key Cryptography—PKC 2003, LCNS, Vol. 2567, pp. 18-30, Springer-Verlag, 2003, an identity-based digital signature method that employs bilinear pairings is disclosed. The method can be described as follows. G1 and G2 are groups which have prime order r, meaning that there are exactly r elements in each group. The bilinear pairing e is a map from G1×G2 into a third group G3. This pairing has the properties that for an integer i and elements M,M1 and M2 in G1 and elements N, N1 and N2 in G2, e(iM,N)=e(M,iN)=e(M,N)i, e(M1+M2,N)=e(M1,N)+e(M2,N), and e(M,N1+N2)=e(M,N1) e(M,N2). H(m,U) is a cryptographic hash function that maps a bit string m and a point U in G1 to an integer between 1 and r.
The first step of the Cha-Cheon method is selecting an element T in G2. Then, selecting an integer s in the range [1, r−1] and keeping it as a secret. Then, computing P equal to sT. Then, P and T are made public. Then, a user is given a public key Q and a private key C, where Q is an element of G1 that is derived from the user's identifier, and where C is equal to sQ. To sign a message m, a signer selects an integer t in the range [1, r−1]. Then, the signer generates U equal to tQ and generates V equal to (t+H(m,U))C. The digital signature is (U,V).
To verify a digital signature (U,V) generated by the Cha-Cheon method using a message m, a verifier derives the signer's public key Q from the signer's identifier and computes h equal to H(m,U). If e(U+hQ,P) is equal to e(V,T) then the digital signature is valid and the message is accepted as being as the sender intended. Otherwise, the digital signature is invalid, and the message is not accepted.
In an article entitled “A New ID-Based Signature with Batch Verification,” by J. Cheon et al., Cryptology ePrint Archive, Report 2004/131, 2004, http://eprint.iacr.org/, a batch verification method for an identity-based digital signature is disclosed. This method uses partially aggregate digital signatures, which are shorter than those in a typical batch of digital signatures. However, using such digital signatures does not provide sufficient information to identify individual invalid digital signatures in a batch.
U.S. Pat. No. 5,347,581, entitled “VERIFICATION PROCESS FOR A COMMUNICATION SYSTEM,” discloses a method of batch verification of digital signatures and tree searching for invalid digital signatures. However, U.S. Pat. No. 5,347,581 does not disclose an efficient method for pruning the tree as does the present invention. U.S. Pat. No. 5,347,581 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,245,718, entitled “LOW BANDWIDTH ZERO KNOWLEDGE AUTHENTICATION PROTOCOL AND DEVICE,” discloses a method of verifying a batch of identities by calculating a product of the public keys of the identities in question. However, U.S. Pat No. 7,245,718 does not disclose a method for identifying invalid signatures in an invalid batches as does the present invention. U.S. Pat. No. 7,245,718 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application No. 20050005125, entitled “APPARATUS AND METHOD FOR GENERATING AND VERIFYING ID-BASED BLIND SIGNATURE BY USING BILINEAR PAIRINGS,” discloses a device for and method of batch verification of digital signatures using a process similar to that of U.S. Pat. 5,347,581. U.S. patent application No. 20050005125 does not disclose a method of identifying invalid digital signatures in invalid batches as does the present invention. U.S. patent application No. 20050005125 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application No. 20050193048, entitled “METHOD TO GENERATE, VERIFY AND DENY AN UNDENIABLE SIGNATURE,” discloses a method of batch verification involving a challenge parameter, a challenge value generated from the challenge parameters, and a commitment value. The present invention does not employ challenge parameters, a challenge value, and a commitment value as does U.S. patent application No. 20050193048. U.S. patent application No. 20050193048 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application No. 20070028114, entitled “VERIFICATION OF IDENTITY BASED SIGNATURES,” discloses a method of batch verification of digital signatures by aggregating elements of the signatures. U.S. patent application No. 20070028114 does not disclose a method of identifying invalid digital signatures in invalid batches as does the present invention. U.S. patent application No. 20070028114 is hereby incorporated by reference into the specification of the present invention.